home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / LIBIP / LLIST.C < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  9.8 KB  |  460 lines
  1. /* 
  2.  * llist.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * LLIST
  11.  *
  12.  * manipulations of doubly linked lists:
  13.  *   several lists may be active 
  14.  *
  15.  * ref: 
  16.  *   R. Sessions
  17.  *   "Reusable Data Structures For C", sects. 3.4, 5.6, 7.1;
  18.  *   Prentice Hall, Englewood Cliffs, NJ, 1989;
  19.  *
  20.  * note:
  21.  *   pointers to struct itemtype, passed in the argument list to
  22.  *   several list manipulation functions in this module (see e.g. 
  23.  *   lladd()), are mapped onto pointers to char!! (see Sessions, p.38); 
  24.  *   this procedure was found to be robust when compiling with the small 
  25.  *   model of MSC-5.1 which employs near (or 2byte) pointers, but found 
  26.  *   to lead to ill-defined conditions when compiling with the large 
  27.  *   model which employs far (or (2+2)byte) pointers; in the latter case, 
  28.  *   a pertinent compiler warning message is given concerning the 
  29.  *   malloc() calls in llcrlink():
  30.  *   ->C4017: cast of int expression to far pointer!! 
  31.  *   for the small memory model, malloc() maps to _fmalloc(), 
  32.  *   in the small model to _nmalloc();
  33.  *   -->a magic quickfix was found:
  34.  *      when gmod() is employed, this problem is not observed!!
  35.  *
  36.  *   to specify the currently active list, the calling routine may
  37.  *   employ a special function llsetlist() in which case a static
  38.  *   variable static struct linklist *list is required; to activate
  39.  *   this option, set SETLIST;
  40.  *   alternatively, the active list may be explicitly specified
  41.  *   in the argument list to the list manipulation functions 
  42.  *   (see Sessions, pp.47 - 49); this option is used here and
  43.  *   requires that SETLIST be undefined
  44.  *
  45.  *   a similar choice of procedure applies to the specification
  46.  *   of the appropriate matching function (see Sessions, sect 5.4);
  47.  *   here, it is specified via the function llsetmatch(); if this
  48.  *   method is to be used, struct linklist (in lldef.h) must contain 
  49.  *   a field specifying this function: int (*match) (); this method 
  50.  *   is recommended when it may be assumed that at any given time a 
  51.  *   linked list only has one associated matching function;
  52.  *   alternatively, the pertinent matching function may be designated
  53.  *   in the argument list to the function llsearch()
  54.  *
  55.  */
  56. #include <stdio.h>
  57. #include <string.h>
  58. #include <malloc.h>
  59. #include "lldef.h"
  60.  
  61.  
  62. #undef    SETLIST                  /* set this switch to activate llsetlist() */
  63. #undef    LLDEBUG
  64.  
  65.  
  66. /*
  67.  * specify active list
  68.  */
  69. #ifdef SETLIST
  70. void
  71. llsetlist (newlist)
  72.      struct linklist *newlist;
  73. {
  74.  
  75.   list = newlist;
  76. }
  77.  
  78. #endif
  79.  
  80. /*
  81.  * specify matching function pertinent to current application
  82.  */
  83. void
  84. llsetmatch (numatch, list)
  85.      int (*numatch) ();
  86.      struct linklist *list;
  87. {
  88.   list->match = numatch;
  89. }
  90.  
  91.  
  92. /*
  93.  * determine size of data item to manipulated
  94.  */
  95. void
  96. llsetsize (size, list)
  97.      int size;
  98.      struct linklist *list;
  99. {
  100.   list->itemlength = size;
  101. }
  102.  
  103.  
  104. /*
  105.  * memory to memory transfer (MSC 5.1)
  106.  */
  107. void
  108. moveitem (src_addr, dest_addr, length)
  109.      char *src_addr, *dest_addr;
  110.      int length;
  111. {
  112.   char *retval;
  113.  
  114.   retval = memmove (dest_addr, src_addr, length);
  115.  
  116. }
  117.  
  118.  
  119.  
  120. /*
  121.  * memory allocation for a new link (see Sessions, pp.39-41, p.49)
  122.  */
  123. struct linktype *
  124. llcrlink (list)
  125.      struct linklist *list;
  126. {
  127.   struct linktype *link;
  128.  
  129.   link = (struct linktype *) malloc (sizeof (struct linktype));
  130. /*      link->item = (char near *)_nmalloc(list->itemlength); */
  131.   link->item = (char *) malloc (list->itemlength);
  132.  
  133. #ifdef LLDEBUG
  134.   printf ("...LLCRLINK:(char *)link->item = %p\n", link->item);
  135. #endif
  136.  
  137.   return (link);
  138. }
  139.  
  140.  
  141. /*
  142.  * initialize empty list
  143.  */
  144. void
  145. llzero (list)
  146.      struct linklist *list;
  147. {
  148.   list->head = list->tail = list->clp = NULL;
  149.   list->listlength = 0;
  150. }
  151.  
  152.  
  153. /*
  154.  * initialize linked list with an item
  155.  */
  156. void
  157. llinit (newitem, list)
  158.      char *newitem;
  159.      struct linklist *list;
  160. {
  161.  
  162.   /* there is only one link (node) in list */
  163.   list->head = list->tail = list->clp = llcrlink (list);
  164.   if (list->clp == NULL) {
  165.     printf ("\n...LLINIT: memory allocation failed\n");
  166.     return;
  167.   }
  168. #ifdef LLDEBUG
  169.   printf ("...LLINIT:  (char *)newitem = %p\n", newitem);
  170.   printf ("    (linktype *)newlink = %p\n", list->clp);
  171. #endif
  172.  
  173.  
  174.   list->clp->next = list->clp->previous = NULL;  /* no other links */
  175.  
  176.   moveitem (newitem, list->clp->item, list->itemlength);  /* mv item */
  177. /*      memmove(list->clp->item, newitem, list->itemlength); */
  178.  
  179.   list->listlength = 1;         /* init. listlength */
  180. }
  181.  
  182.  
  183. /*
  184.  * set the current link ptr (clp) to point to the top (head) of the list
  185.  */
  186. void
  187. llhead (list)
  188.      struct linklist *list;
  189. {
  190.  
  191.   list->clp = list->head;
  192. }
  193.  
  194.  
  195. /*
  196.  * set the current link ptr (clp) to point to the end (tail) of the list
  197.  */
  198. void
  199. lltail (list)
  200.      struct linklist *list;
  201. {
  202.  
  203.   list->clp = list->tail;
  204. }
  205.  
  206.  
  207. /*
  208.  * set the current link ptr to the next link, returning False if 
  209.  * clp is pointing to the tail (end of list), True otherwise
  210.  */
  211. Boolean
  212. llnext (list)
  213.      struct linklist *list;
  214. {
  215.  
  216.   if (list->clp->next == NULL)
  217.     return (False);
  218.   else {
  219.     list->clp = list->clp->next;
  220.     return (True);
  221.   }
  222. }
  223.  
  224.  
  225. /*
  226.  * set the current link ptr to the previous link, returning False if 
  227.  * clp is pointing to the tail
  228.  */
  229. Boolean
  230. llprevious (list)
  231.      struct linklist *list;
  232. {
  233.  
  234.   if (list->clp->previous == NULL)
  235.     return (False);
  236.   else {
  237.     list->clp = list->clp->previous;
  238.     return (True);
  239.   }
  240. }
  241.  
  242.  
  243.  
  244. /*
  245.  * retrieve the item pointed to by the current link ptr and place it 
  246.  * into a memory location specified as an argument
  247.  */
  248. void
  249. llretrieve (newitem, list)
  250.      char *newitem;
  251.      struct linklist *list;
  252. {
  253.  
  254.   moveitem (list->clp->item, newitem, list->itemlength);
  255. }
  256.  
  257.  
  258. /*
  259.  * search list for a given item, returning True if found, False otherwise
  260.  * (see Sessions, sect. 3.5, p.30  ca_check(), 
  261.  *             sect. 5.4, pp.53/54  llcheck() )
  262.  */
  263. Boolean
  264. llsearch (desired_item, list)
  265.      char *desired_item;
  266.      struct linklist *list;
  267. {
  268.   Boolean retval = False;
  269.   Boolean MatchStatus = False;
  270.  
  271.  
  272.   llhead (list);
  273.   do {
  274.     if ((*list->match) (list->clp->item, desired_item)) {
  275.       printf ("\n...found item in llist\n");
  276.       MatchStatus = True;
  277.     }
  278.   } while ((MatchStatus != True) && ((retval = llnext (list)) == True));
  279.  
  280.  
  281.   return (MatchStatus);
  282. }
  283.  
  284.  
  285.  
  286.  
  287. /*
  288.  * add (insert) a new link containing a newitem immediately
  289.  * following the link pointed to by the current link ptr
  290.  */
  291. void
  292. lladd (newitem, list)
  293.      char *newitem;
  294.      struct linklist *list;
  295. {
  296.   struct linktype *newlink;
  297.   int retval;
  298.  
  299.  
  300. /* if empty, initialize list */
  301.   if ((retval = ll_length (list)) == 0) {
  302.     llinit (newitem, list);
  303.     return;
  304.   }
  305.  
  306. /* create new link */
  307.   if ((newlink = llcrlink (list)) == NULL) {
  308.     printf ("\n...LLADD: memory allocation failed\n");
  309.     return;
  310.   }
  311. #ifdef LLDEBUG
  312.   printf ("...LLADD:   (char *)newitem = %p\n", newitem);
  313.   printf ("    size of ptr to char = %d\n", sizeof (char *));
  314.   printf ("    (linktype *)newlink = %p\n", newlink);
  315. #endif
  316.  
  317.  
  318.   moveitem (newitem, newlink->item, list->itemlength);
  319.   list->listlength++;
  320.  
  321.  
  322. /* reset list pointers */
  323.   newlink->next = list->clp->next;
  324.   newlink->previous = list->clp;
  325.  
  326.   if (list->tail == list->clp)  /* handle appending new tail */
  327.     list->tail = newlink;
  328.   else
  329.     list->clp->next->previous = newlink;
  330.  
  331.   list->clp->next = newlink;
  332.   list->clp = newlink;
  333. }
  334.  
  335.  
  336. /*
  337.  * add (insert) a new link containing a newitem immediately
  338.  * preceding (!) the head of the list
  339.  */
  340. void
  341. lladdhead (newitem, list)
  342.      char *newitem;
  343.      struct linklist *list;
  344. {
  345.   struct linktype *newlink;
  346.   int retval;
  347.  
  348. /* if empty, initialize list */
  349.   if ((retval = ll_length (list)) == 0) {
  350.     llinit (newitem, list);
  351.     return;
  352.   }
  353.  
  354. /* create new link */
  355.   if ((newlink = llcrlink (list)) == NULL) {
  356.     printf ("\n...LLADDHEAD: memory allocation failed\n");
  357.     return;
  358.   }
  359.  
  360.   moveitem (newitem, newlink->item, list->itemlength);
  361.   list->listlength++;
  362.  
  363. /* reset list pointers */
  364.   newlink->next = list->head;
  365.   newlink->previous = NULL;
  366.   list->head->previous = newlink;
  367.   list->clp = list->head = newlink;
  368. }
  369.  
  370.  
  371. /*
  372.  * add (insert) a new link containing a newitem immediately
  373.  * preceding(!) the link pointed to by the current link ptr
  374.  * (this is generalization of routine lladdhead() represents
  375.  * the analog of routine lladd() )
  376.  */
  377. void
  378. lladdprev (newitem, list)
  379.      char *newitem;
  380.      struct linklist *list;
  381. {
  382.   struct linktype *newlink;
  383.   int retval;
  384.  
  385. /* if empty, initialize list */
  386.   if ((retval = ll_length (list)) == 0) {
  387.     llinit (newitem, list);
  388.     return;
  389.   }
  390.  
  391. /* create new link */
  392.   if ((newlink = llcrlink (list)) == NULL) {
  393.     printf ("\n...LLADDPREV: memory allocation failed\n");
  394.     return;
  395.   }
  396.  
  397.   moveitem (newitem, newlink->item, list->itemlength);
  398.   list->listlength++;
  399.  
  400. /* reset list pointers */
  401.   newlink->previous = list->clp->previous;
  402.   newlink->next = list->clp;
  403.  
  404.   if (list->head == list->clp)  /* handle insertion of new head */
  405.     list->head = newlink;
  406.   else
  407.     list->clp->previous->next = newlink;
  408.  
  409.   list->clp->previous = newlink;
  410.   list->clp = newlink;
  411. }
  412.  
  413.  
  414. /* 
  415.  * delete the link pointed to by the current link ptr (clp)
  416.  */
  417. void
  418. lldelete (list)
  419.      struct linklist *list;
  420. {
  421.   struct linktype *before, *after;
  422.  
  423.   /* only one link in list */
  424.   if ((list->head == list->clp) && (list->tail == list->clp))
  425.     list->head = list->tail = NULL;
  426.  
  427.   else if (list->head == list->clp) {  /* del head of list */
  428.     list->head = list->head->next;
  429.     list->head->previous = NULL;
  430.   }
  431.   else if (list->tail == list->clp) {  /* del tail of list */
  432.     list->tail = list->tail->previous;
  433.     list->tail->next = NULL;
  434.   }
  435.   else {                        /* del interior link */
  436.     before = list->clp->previous;
  437.     after = list->clp->next;
  438.     before->next = after;
  439.     after->previous = before;
  440.   }
  441.  
  442.   free (list->clp->item);       /* free mem */
  443.   free (list->clp);
  444.  
  445.   list->clp = list->head;       /* del current link */
  446.   list->listlength--;
  447.  
  448. }
  449.  
  450.  
  451. /*
  452.  * return listlength
  453.  */
  454. int
  455. ll_length (list)
  456.      struct linklist *list;
  457. {
  458.   return (list->listlength);
  459. }
  460.